#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Passenger {
    char data[21];
    struct Passenger *Llink;
    struct Passenger *Rlink;
} Passenger;

Passenger *createNode(const char name[]) {
    Passenger *newNode = (Passenger *)malloc(sizeof(Passenger));
    strcpy(newNode->data, name);
    newNode->Llink = NULL;
    newNode->Rlink = NULL;
    return newNode;
}

void addPassenger(Passenger *head, const char name[]) {
    Passenger *p = head->Rlink;
    while (p != NULL && strcmp(p->data, name) < 0) {
        p = p->Rlink;
    }
    if (p == NULL) {
        // Insert at the end
        Passenger *newNode = createNode(name);
        Passenger *tail = head->Llink;
        if (tail == NULL) {
            head->Rlink = newNode;
            newNode->Llink = head;
            head->Llink = newNode;
        } else {
            newNode->Rlink = tail->Rlink;
            newNode->Llink = tail;
            tail->Rlink = newNode;
            head->Llink = newNode;
        }
    } else {
        // Insert in the middle or at the beginning
        Passenger *newNode = createNode(name);
        newNode->Rlink = p;
        newNode->Llink = p->Llink;
        p->Llink = newNode;
        if (newNode->Llink == head) {
            head->Rlink = newNode;
        } else {
            newNode->Llink->Rlink = newNode;
        }
    }
}

void deletePassenger(Passenger *head, const char name[]) {
    Passenger *p = head->Rlink;
    while (p != NULL && strcmp(p->data, name) != 0) {
        p = p->Rlink;
    }
    if (p != NULL) {
        if (p->Rlink == NULL) {
            // Delete the last node
            head->Llink = p->Llink;
        } else {
            p->Rlink->Llink = p->Llink;
        }
        p->Llink->Rlink = p->Rlink;
        free(p);
    }
}

void queryPassenger(Passenger *head, const char name[]) {
    Passenger *p = head->Rlink;
    while (p != NULL && strcmp(p->data, name) != 0) {
        p = p->Rlink;
    }
    if (p != NULL) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
}

void printPassengerList(Passenger *head) {
    Passenger *p = head->Rlink;
    while (p != NULL) {
        printf("%s\n", p->data);
        p = p->Rlink;
    }
}

int main() {
    Passenger *head = (Passenger *)malloc(sizeof(Passenger));
    head->Llink = NULL;
    head->Rlink = NULL;

    char operation[20], name[21];
    while (scanf("%s", operation) != EOF) {
        if (strcmp(operation, "Add") == 0) {
            scanf("%s", name);
            addPassenger(head, name);
        } else if (strcmp(operation, "Delete") == 0) {
            scanf("%s", name);
            deletePassenger(head, name);
        } else if (strcmp(operation, "Query") == 0) {
            scanf("%s", name);
            queryPassenger(head, name);
        } else if (strcmp(operation, "Print") == 0) {
            printPassengerList(head);
        }
    }

    // Free the memory allocated for passengers
    Passenger *p = head->Rlink;
    while (p != NULL) {
        Passenger *temp = p;
        p = p->Rlink;
        free(temp);
    }

    free(head);
    
    return 0;
}
